The present invention relates to a method and system for utilizing computers to discover plans that achieve design goals or sets of design goals in domains.
Applications for systems may include programs that schedule work in factories or plants, that control complex systems such as factories or power plants to maintain design criteria, that plan routing for fleets of trucks, that find plans how to economically and rapidly travel to a desired destination, or that play games and solve puzzles. Such applications typically involve a particular given domain. For example, if one were designing a program to play chess, the domain would be chess, or if one were controlling a factory, the domain would be that particular factory, including the particular layout of the particular machines therein. Aspects of the domain may be represented in a computer program or in data readable by a computer program, so that a computer program can be used to construct plans or to aid humans to construct plans to achieve a variety of goals within the domain. For example, one might want the program to be able to win from a variety of different chess positions, or one might want the program to control a factory to optimally produce a variety of different products, with the particular design goal (say whether to produce 100,000 pencils or 50,000 pens and 10,000 pencils) changing in different runs of the program.
Present day automated systems for finding plans may utilize either search or planners. Both of these methods are typically based on domain independent algorithms, and exploit little of the structure of a particular domain. Search programs typically only have knowledge about their goal in the form of an operator that recognizes when it has been achieved, and a heuristic function that may indicate distance from the goal. Planners typically exploit knowledge encoded in what is called the STRIPS language, but this also may fail to exploit useful structure of particular domains. As a result, these methods often search through many possible sequences of operators that are not relevant to solving specific obstacles, and thus are often not efficient enough to solve problems that one wishes to solve in a reasonable amount of time.
However, many domains of interest have structure which might be efficiently exploited for solution. For example, many problems of interest involve routing in two or three dimensions, so that aspects of the topology of two and three dimensions might be exploited in finding plans. Many domains of interest contain objects that may be affected in ways characteristic of the type of object, and which may sometimes present obstacles to plans. Many domains of interest contain characteristic kinds of obstacles to implementing available actions, and these obstacles may in many cases be fixed by solutions characteristic of the kind of obstacle.